package leetcode;

import java.util.Scanner;

public class LeetCodeMain71 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int[] dp=new int[100005];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= 100000; i++) {
            dp[i]=(dp[i-1]+dp[i-2])%1000000;
        }
        while (in.hasNext()){
            int n=in.nextInt();
            if(n>=30)
                System.out.printf("%06d\n",dp[n]);
            else
                System.out.printf("%d\n",dp[n]);
        }
    }
    public static void main1(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            String string=in.nextLine();
            String[] str=string.split(" ");
            int year=Integer.parseInt(str[0]);
            int month=Integer.parseInt(str[1]);
            int day=Integer.parseInt(str[2]);
            int year1=Integer.parseInt(str[3]);
            int month1=Integer.parseInt(str[4]);
            int day1=Integer.parseInt(str[5]);
            int sum=0;
            int sum1=0;
            int[][] money={{0,0},
                    {31,2},
                    {28,1},
                    {31,1},
                    {30,2},
                    {31,1},
                    {30,2},
                    {31,1},
                    {31,2},
                    {30,2},
                    {31,2},
                    {30,1},
                    {31,2}};
            for (int i = 1; i < money.length; i++) {
                sum1+=money[i][0]*money[i][1];
            }
            if (year1==year){
                if (year%400==0||year%4==0&&year%100!=0){
                    money[2][0]=29;
                }
                if (month==month1){
                    sum=sum+money[month][1]*(day1-day+1);
                }else {
                    for (int i = month+1; i <= month1-1; i++) {
                        sum+=money[i][1]*money[i][0];
                    }
                    sum=sum+money[month][1]*(money[month][0]-day)+money[month1][1]*day1;
                }

            }else {
                for (int i = year+1; i <= year1-1; i++) {
                    if (i%400==0||i%4==0&&i%100!=0){
                        sum++;
                    }
                    sum+=sum1;
                }
                if (year%400==0||year%4==0&&year%100!=0){
                    money[2][0]=29;
                }
                for (int i = month+1; i <= 12; i++) {
                    sum+=money[i][1]*money[i][0];
                }
                sum+=money[month][1]*(money[month][0]-day+1);
                if (year1%400==0||year1%4==0&&year1%100!=0){
                    money[2][0]=29;
                }else {
                    money[2][0]=28;
                }
                for (int i = 1; i <= month1-1; i++) {
                    sum+=money[i][1]*money[i][0];
                }
                sum+=money[month1][1]*day1;
            }
            System.out.println(sum);
        }
    }

}
